740. 删除并获得点数

进阶版的 打家劫舍

具体 参考题解

总之就是计算出 sum 数组后就是 打家劫舍 那个逻辑

func deleteAndEarn(nums []int) int {
    maxVal := 0
    for _, num := range nums {
        maxVal = max(maxVal, num)
    }
    // 之所以 sum 数组创建大小是 maxVal，是因为 sum 的索引就是 num 值
    sum := make([]int, maxVal + 1)
    for _, num := range nums {
        sum[num]+=num
    }

    return _rob(sum)
}

func _rob(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i := 2; i < n; i++ {
        dp[i] = max(dp[i-2] + nums[i], dp[i-1])
    }
    return dp[n-1]
}


func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}